package com.acwing.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定你一个长度为 n 的整数数列。
 *
 * 请你使用快速排序对这个数列按照从小到大进行排序。
 *
 * 并将排好序的数列按顺序输出。
 * 快速排序 时间复杂度O(N* logN) 最坏情况下O（n^2） 空间复杂度O(logN) 最坏O(N)类似于树的高度 稳定性 不稳定
 * User:yxd
 * Date:2022-01-11
 * Time:0:26
 */
import java.util.*;
public class Quick {
    static int N = 100005;
    static int q[] = new int[N];//确定数组的大小
    static int n;
    //快速排序模板
    public static  void quick_sort(int l,int r){
        if(l >= r)return;//没有元素或者只有一个元素则不需要排序
        int x = q[l];//分界点 可以随便定义
        int i = l -1;//左边临界点
        int j = r + 1;//右边分界点 分别扩了一位保证 临界不出问题
        while(i < j){
            do i++;while(q[i] < x);//走到大于等于x的值的时候停下来
            do j--;while(q[j] > x);//走到小于等于x的值的时候停下来
            if(i < j){//此时正好q[i]是大于等于x 的q[j]是小于等于x的交换之后  正好
                int h = q[i];
                q[i] = q[j];
                q[j] = h;
            }
        }
        quick_sort(l,j);//递归左半边  边界一定保证一致 上面j 下面就j+1 但是j分界的时候分界点不能是q[r]否则会出错
        quick_sort(j + 1,r);//递归右半边
    }

    public static void main(String[] args){
        /*Scanner input = new Scanner(System.in);
        n = input.nextInt();
        for(int i = 0;i < n; i++){
            q[i] = input.nextInt();
        }*/
        int[] w = {15,24,1,14,26,3};
        /*int[] w = new int[20_0000];
        for (int i = 0; i < w.length; i++) {
            w[i] = i;
        }//二十万个有序数组测执行时间
        long start = System.currentTimeMillis();//开始时间
        quickSort1(w);
        long end = System.currentTimeMillis();//结束时间
        System.out.println(end - start);*/
        //quick_sort(0,n - 1);
        quickSort1(w);//非递归
        /*for(int i = 0;i < n;i++){
            System.out.print(w[i] + " ");
        }
        System.out.println();*/
        System.out.println(Arrays.toString(w));
    }
    public static void quickSort(int[] array){
        quick(array,0,array.length - 1);
    }
    public static void insertSort(int[] array,int left,int right){
        for (int i = 1; i <= right; i++) {
            int j = i - 1;
            int tmp = array[i];
            for (; j >= left; j--) {
                if(array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = tmp;//j回退到了小于0的地方
        }
    }
    public static void quick(int[] array,int left,int right){
        if(left >= right)return;
        //3.也可以在区间越来越小的时候使用直接插入排序来排序优化（直接拆入排序越趋于有序越快）
        if(right - left + 1 < 40){
            insertSort(array, left, right);
        }
        //找基准之前需要尽量保证基准的左右都有值，保证不会一边没有数，因此可以采用随机取数的方式，
        //1. 但这种方法又太过于随机了，无法保证取的值是否左右有值，因此我们采用2.几数取中法
        //从left，right，mid中取中间大的值作为基准,然后和left的值交换
        int midIndex = findPivot(array, left, right);
        int tmp = array[midIndex];
        array[midIndex] = array[left];
        array[left] = tmp;

        int pivot = partition(array,left,right);
        quick(array,left,pivot - 1);
        quick(array,pivot + 1,right);
    }
    public static  int findPivot(int[] array,int left,int right){
        int mid = left + (right - left) / 2;
        if(array[right] > array[left]){
            if(array[left] > array[mid]){
                return left;
            }else if(array[right] < array[mid]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }
    //挖坑法  找基准
    public static int partition(int[] array,int left,int right){
        int tmp = array[left];
        while(left < right){
            while(left < right && array[right] >= tmp){
                right --;
            }//右边找到小于这个数的值，并交换
            array[left] = array[right];
            while(left < right && array[left] <= tmp){
                left ++;
            }//左边找到大于这个数的值，并交换
            array[right] = array[left];

        }
        array[left] = tmp;//最后埋坑
        return left;
    }



    //非递归的快速排序
    public static void quickSort1(int[] array){
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array,left,right);
        Stack<Integer> stack = new Stack<>();
        if(pivot > left + 1){
            //左边两个元素
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(right  - 1 > pivot){
            //右边两个元素
            stack.push(pivot + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();//第一个出栈的是右边的
            left = stack.pop();//然后是新的left，重复这样的操作
            pivot = partition(array,left,right);
            if(pivot > left + 1){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(right  - 1 > pivot){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }

    }
}

